#include <cstdio>

int n, m, d[ 101 ][ 101 ], pow[ 101 ], f[ 10001 ], sum;

void init( )
{
    int i, j, k, s, e, c;
    scanf("%d%d", &n, &m);
    for ( i = 0; i <= n; i++ )
        for ( j = 0; j <= n; j++ )
            d[ i ][ j ] = 0xfffffff;
    sum = 0;
    for ( i = 0; i < m; i++ )
    {
        scanf("%d%d%d", &s, &e, &c);
        if ( d[ s ][ e ] > c )
            d[ s ][ e ] = d[ e ][ s ] = c;
    }
    for ( i = 1; i <= n; i++ )
    {
        scanf("%d", &pow[ i ]);
        sum += pow[ i ];
    }
    for ( k = 0; k <= n; k++ )
        for ( i = 0; i <= n; i++ )
            for ( j = 0; j <= n; j++ )
                if ( d[ i ][ j ] > d[ i ][ k ] + d[ k ][ j ] )
                    d[ i ][ j ] = d[ i ][ k ] + d[ k ][ j ];
}

void work( )
{
    int i, j, k, minc = 0xfffffff;
    for ( i = 0; i <= sum; i++ )
        f[ i ] = 0xfffffff;
    f[ 0 ] = 0;
    for ( i = 1; i <= n; i++ )
        for ( j = sum; j >= pow[ i ]; j-- )
            if ( f[ j ] > f[ j - pow[ i ] ] + d[ 0 ][ i ] )
                f[ j ] = f[ j - pow[ i ] ] + d[ 0 ][ i ];
    for ( i = sum / 2 + 1; i <= sum; i++ )
        if ( minc > f[ i ] )
            minc = f[ i ];
    if ( minc == 0xfffffff )
        puts("impossible");
    else
        printf("%d\n", minc);
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
    }
    return 0;
}
